package sort;

/**
 *  快速排序算法：
 *  (1)首先设定一个分界值，通过该分界值将数组分成左右两部分。
 *  (2)将大于等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时
 *  ----左边部分中各元素都小于等于分界值，而右边部分中各元素都大于等于分界值。
 *  (3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，
 *  ----同样将左边放置较小值，右边放置较大值。右侧的数组也可以做类似处理。
 *  (4）重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归好右侧部分的顺序。当
 *  左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
 *
 *
 */
public class QuickSort {
    public static void main(String[] args){
        int[] arr = new int[]{23,2,4,5,2,55,32,6,7,1};
        quickSort(arr,0,arr.length-1);
        for(int temp:arr){
            System.out.print(temp+"\t");
        }
    }

    /**
     * 快速排序
     * @param arr 要排序的数组
     * @param leftIndex  左侧下标
     * @param rightIndex 右侧小标
     */
    public static void quickSort(int[] arr,int leftIndex,int rightIndex){
        int  leftTempIndex = leftIndex;
        int rightTempIndex = rightIndex;
        int middleData = arr[(leftIndex+rightIndex)/2];//从中间将坐标一分为2份
        while(leftTempIndex < rightTempIndex){//左侧临时坐标与右侧临时坐标到一块的时候也就是数据排序完
            // /如果说左侧数据小于中间数据左侧下标一直向后移动
            // 直到遇到一个左侧数据比中间数据大的数据或者循环移动到中间位置
            while(arr[leftTempIndex]<middleData){//
                ++leftTempIndex;
            }
            // /如果说右侧数据小于中间数据右侧下标一直向后移动
            // 直到遇到一个右侧数据比中间数据大的数据或者循环移动到中间位置
            while(arr[rightTempIndex]>middleData){
                --rightTempIndex;
            }
            if(leftTempIndex<=rightTempIndex){
                int  temp=arr[leftTempIndex];
                arr[leftTempIndex]=arr[rightTempIndex];
                arr[rightTempIndex] = temp;
                --rightTempIndex;
                ++leftTempIndex;
            }
        }
        if(leftTempIndex==rightTempIndex){
            leftTempIndex++;
        }
        if(leftIndex<rightTempIndex){
            quickSort(arr,leftIndex,leftTempIndex);//递归调用
        }
        if(leftTempIndex<rightIndex){
            quickSort(arr,rightTempIndex+1,rightIndex);//递归调用
        }
    }
}
